/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-07
 * Time: 20:10
 */
public class HashBuck {
    static class Node {
        public int key;
        public int value;
        public Node next;
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }

    public Node[] array;
    public int usedSize;
    public static final double DEFAULT_LOAD_FACTOR=0.75;
    public HashBuck(){
        this.array=new Node[10];
    }

    /**
     * 放置元素
     * @param key
     * @param value
     */
    public void put(int key,int value){
        //找位置
        int hash=key % array.length;
        //看看是否有key值相同的情况,有就更新value
        Node cur=array[hash];
        while(cur!=null){
            //有key值相同的情况
            if(cur.key==key){
                cur.value=value;
                return ;
            }
            cur=cur.next;
        }
        //没有key值与之相同,头插
        if(array[hash]==null){
            //该位置没有节点
            array[hash]=new Node(key,value);
        }else{
            Node newNode=new Node(key,value);
            newNode.next=array[hash];
            array[hash]=newNode;
        }
        this.usedSize++;
        //检查负载因子
        double loadFactor=1.0*usedSize/array.length;
        //如果大于负载因子需要重新哈希
        if(loadFactor>DEFAULT_LOAD_FACTOR){
            //先扩容
            Node [] newArray=new Node[array.length*2];
            //重新哈希
            for (int i = 0; i < array.length; i++) {
                Node temp=array[i];
                while(temp!=null){
                    Node tempNext=temp.next;
                    Node node=temp;
                    int newHash=node.key%newArray.length;
                    node.next=newArray[newHash];
                    newArray[newHash]=node;
                    temp=tempNext;
                }
            }
            //数组交换为新的数组
            this.array=newArray;
        }

    }

    /**
     * 根据key值获取value
     * @param key
     * @return
     */
    public int get(int key){
        int hash=key%this.array.length;
        Node cur=array[hash];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            cur=cur.next;
        }
        return -1;
    }
}

